﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.Problems.ExactCover;
using Algoritmia.Schemes;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;
using DLX = Algoritmia.Problems.ExactCover.DLX;

namespace Algoritmia.Problems.Puzzles.NQueens
{
    public class NQueensDLX2Solver
    {
        private readonly Func<Lists.IList<Lists.IList<int>>> _createMatrix;
        private readonly Func<Lists.IList<Tuple<int, int>>> _createRowsCoding;
        private readonly Func<Lists.IList<int>> _createIntegersList;

        private BacktrackingEnumerator<DLX.State2, DLX.Cell, Lists.IList<int>> _solver;

        public NQueensDLX2Solver(Func<Lists.IList<Lists.IList<int>>> createMatrix = null,
                                 Func<Lists.IList<Tuple<int,int>>> createRowsCoding = null,
                                 Func<Lists.IList<int>> createIntegersList = null)
        {
            _createMatrix = createMatrix ?? (() => AlgoritmiaFactory.Lists<Lists.IList<int>>.Default);
            _createRowsCoding = createRowsCoding ?? (() => AlgoritmiaFactory.Lists<Tuple<int, int>>.Default);
            _createIntegersList = createIntegersList ?? (() => AlgoritmiaFactory.Lists<int>.Default);
        }

        public Lists.IList<int> FirstSolution(int n)
        {
            Lists.IList<Lists.IList<int>> matrix;
            Lists.IList<Tuple<int, int>> rowsCoding;
            NQueensToMatrix(n,out matrix, out rowsCoding);
            _solver = new BacktrackingEnumerator<DLX.State2, DLX.Cell, Lists.IList<int>>((space, i, d, f) => SelectedNQueens(f.Selected, rowsCoding));
            return _solver.First(new DLX2StateSpace(matrix, Enumerable.Range(0, 2*n).ToAlgoritmiaList()));
        }

        private void NQueensToMatrix(int N, out Lists.IList<Lists.IList<int>> matrix,out Lists.IList<Tuple<int,int>> rowsCoding)
        {
            matrix = _createMatrix();
            rowsCoding = _createRowsCoding();
            for(int row = 0; row < N; row++)
            {
                for(int col = 0; col < N; col++)
                {
                    var list = _createIntegersList();
                    list.Add(row);
                    list.Add(N+col);
                    list.Add(2 * N + col - row + N - 1);
                    list.Add(2 * N + 2 * N - 1 + col + row);
                    matrix.Add(list);
                    rowsCoding.Add(new Tuple<int, int>(row,col));
                }
            }
        }

        private static Lists.IList<int> SelectedNQueens(IEnumerable<int> selected, Lists.IList<Tuple<int,int>> rowsCoding)
        {
            if ( selected != null)
            {
                var list = selected.Select(e => rowsCoding[e]).ToList();
                list.Sort();
                return list.Select(tp => tp.Item2).ToAlgoritmiaList();
            }
            else
            {
                return null;
            }
        }
    }
}
